package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/3 22:39
 */
public class 路径总和III {
    static int res;
    static int N = (int) 1e4;
    static HashMap<Long, Integer> map = new HashMap<>(N);

    {
        res = 0;
        map.clear();
        map.put(0L, 1);
    }

    public int pathSum(TreeNode root, int targetSum) {

        dfs(root, targetSum, 0);
        return res;
    }

    void dfs(TreeNode root, int x, long sum) {
        if (root == null)
            return;
        sum += root.val;
        int v = map.getOrDefault(sum - x, 0);
        res += v;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        dfs(root.left, x, sum);
        dfs(root.right, x, sum);
        map.put(sum, map.getOrDefault(sum, 0) - 1);

    }

}
